package leetcode.offer_two_special.hash;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

/**
 * @author mazouri
 * @create 2021-09-09 20:51
 */
public class RandomizedSet {
    //key:num value:location
    HashMap<Integer, Integer> map;
    ArrayList<Integer> nums;

    /**
     * Initialize your data structure here.
     */
    public RandomizedSet() {
        map = new HashMap<>();
        nums = new ArrayList<>();
    }

    /**
     * Inserts a value to the set. Returns true if the set did not already contain the specified element.
     */
    public boolean insert(int val) {
        if (map.containsKey(val)) return false;

        map.put(val, nums.size()-1);
        nums.add(val);
        return true;
    }

    /**
     * Removes a value from the set. Returns true if the set contained the specified element.
     */
    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;

        Integer removeIndex = map.get(val);
        Integer lastNum = nums.get(nums.size() - 1);
        map.put(lastNum, removeIndex);
        map.remove(val);
        nums.set(removeIndex, lastNum);
        nums.remove(nums.size() - 1);
        return true;
    }

    /**
     * Get a random element from the set.
     */
    public int getRandom() {
        return nums.get(new Random().nextInt(nums.size()));
    }
}
